package com.code.snippet.wdg;

public class WeightedDirectedGraph {
    private final int MAX_VERTS=20;//最大顶点数
    private final int INFINITY=1000000;//无限大的值，用于表示不连通的权值
    private Vertex[] vertexList;//顶点数组
    private int [][]adjMat;//顶点关系的领接矩阵(邻接矩阵的每行或者每列的位置跟顶点数组是对应的)
    private int nVerts;//当前顶点个数
    private int nTree;//记录当前访问的顶点数量，控制循环
    private DistanceParent [] sPath;//保存路径（即保存有向边的数组）
    private int currentnVert;//标志访问的当前顶点，该值为当前顶点索引值
    private int startToCurrent;//标志到currentnVert点的边的权值
    public WeightedDirectedGraph() {//初始化图
        vertexList=new Vertex[MAX_VERTS]; //初始化顶点数组
        adjMat=new int [MAX_VERTS][MAX_VERTS] ;//初始化邻接矩阵
        for(int j=0;j<MAX_VERTS;j++)
            for(int i=0;i<MAX_VERTS;i++)
                adjMat[j][i]=INFINITY;
        nVerts=0;//初始化当前顶点个数
        nTree=0;
        sPath=new DistanceParent[MAX_VERTS];


    }
    //向顶点数组中添加顶点对象（lab为顶点对象的label属性值）
    public void addVertex(char lab) {
        vertexList[nVerts++]=new Vertex(lab);//建立lab对象，往数组内添加
    }
    //添加边（向邻接矩阵中改变权值）
    public void addEdge(int start,int end,int weight) {
        //因为是有向图
        adjMat[start][end]=weight;

    }
    //最短路径计算
    public void path() {
        int startTree=0;//起始顶点为0
        vertexList[startTree].isVisited=true;
        nTree=1;
        for(int j=0;j<nVerts;j++) {//访问当前顶点的邻接点
            int tempDist=adjMat[startTree][j];//获取边的权值
            sPath[j]=new DistanceParent(startTree,tempDist);  //将有向边的存入数组中.起始点是startTree，权值是tempDist，放入数组的索引为j的位置

        }//初始化sPath数组

        //不断循环改变sPath数组的值
        //找最短路径
        //获取当前点之前需要比较，获取边权值最小的那个点
        while(nTree<nVerts) {//需要遍历nVerts次，当nTree为0时，访问了一个顶点，当访问nVerts个时，nTree为nVerts-1
            int indexMin=getMin();//在sPath（有向边数组）中获取权值最小的到达点
            int minDist=sPath[indexMin].distance;//获取有向边的权值
            if(minDist==INFINITY) {//因为如果在sPath数组中获取的最小的边值是无穷大，说明该图是不通的
                System.out.println("不通");
                break;
            }else {
                currentnVert=indexMin;//将该点又作为源点开始循环
                startToCurrent=sPath[indexMin].distance;//有向边数组中的值是总距离
            }
            vertexList[currentnVert].isVisited=true;
            nTree++;
            //更新最小路径数组(如果当前点的startToCurrent加上当前点到其他点的值小，就需要更新)
            adj_sPath();
        }
        displayPath();
        nTree=0;
        for(int j=0;j<nVerts;j++)
            vertexList[j].isVisited=false;

    }
    public void adj_sPath() {
        int column=1;
        while(column<nVerts) {//更新除了遍历过的顶点
            if(vertexList[column].isVisited) {
                column++;
                continue;
            }//遍历过的顶点就不更新这条记录
            int currentToFringe=adjMat[currentnVert][column];//终点是column
            int startToFringe=startToCurrent+currentToFringe;//startToCurrent为currentnVert点之前的距离
            int sPathDist=sPath[column].distance;
            if(startToFringe<sPathDist) {//更新
                sPath[column].parentVert=currentnVert;
                sPath[column].distance=startToFringe;
            }
            column++;
        }
    }
    //找到一个当前顶点的联通的点,而且是权值最小的边
    public int getMin() {
        int minDist=INFINITY;//记录获取到的顶点的索引
        int indexMin=0;//记录获取到的索引值
        for(int j=1;j<nVerts;j++) {//在数组中找某个顶点
            if(!vertexList[j].isVisited && sPath[j].distance<minDist) {//该顶点是没有被访问过的，而且权值是比minDist更小的
                minDist=sPath[j].distance;//获取该值
                indexMin=j;//获取该点的索引
            }
        }
        return indexMin;

    }
    public void displayPath() {
        for(int j=0;j<nVerts;j++) {//遍历，
            System.out.print(vertexList[j].label+"=");//顶点标记
            if(sPath[j].distance==INFINITY) {//查询顶点是否在sPath有边
                System.out.print("没有");
            }else {
                System.out.print(sPath[j].distance);//有的话就输出
            }
            char parent=vertexList[sPath[j].parentVert].label;//查询该顶点的父顶点
            System.out.println("("+parent+")");
        }
        System.out.println();
    }
}
